{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Number and Its Reverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumOfNumberAndReverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #反转之后的数字和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>非负</strong> 整数 <code>num</code> 。如果存在某个 <strong>非负</strong> 整数 <code>k</code> 满足 <code>k + reverse(k) = num</code>&nbsp; ，则返回 <code>true</code> ；否则，返回<em> </em><code>false</code> 。</p>\n",
    "\n",
    "<p><code>reverse(k)</code> 表示 <code>k</code> 反转每个数位后得到的数字。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 443\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>172 + 271 = 443 ，所以返回 true 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 63\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>63 不能表示为非负整数及其反转后数字之和，返回 false 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 181\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>140 + 041 = 181 ，所以返回 true 。注意，反转后的数字可能包含前导零。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= num &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-number-and-its-reverse](https://leetcode.cn/problems/sum-of-number-and-its-reverse/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-number-and-its-reverse](https://leetcode.cn/problems/sum-of-number-and-its-reverse/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['443', '63', '181']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        return any(x + int(str(x)[::-1]) == num for x in range(num + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num + 1):\n",
    "            j = int(str(i)[::-1])\n",
    "            if i + j == num:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num + 1):\n",
    "            rev,x= 0,i\n",
    "            while x:\n",
    "                rev = rev * 10 + x % 10\n",
    "                x //= 10\n",
    "            if i + rev == num:\n",
    "                return True\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        return any(x + int(''.join(reversed(str(x)))) == num for x in range(num + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for a in range(num,num//2-1,-1):\n",
    "            b = str(a)\n",
    "            b = int(b[::-1])\n",
    "            if a + b == num:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for x in range((num + 1) // 2, num + 1):\n",
    "            y = int(str(x)[::-1])\n",
    "            if x + y == num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for integer in range(num + 1):\n",
    "            if integer + reverse(integer) == num:\n",
    "                return True \n",
    "        return False \n",
    "\n",
    "def reverse(integer):\n",
    "    reverse_value = 0 \n",
    "    while integer:\n",
    "        reverse_value = reverse_value * 10 + integer % 10\n",
    "        integer //= 10\n",
    "    return reverse_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        return any(i + int(str(i)[::-1]) == num for i in range(0, num + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for a in range(num,num//2-1,-1):\n",
    "            b = str(a)\n",
    "            b = int(b[::-1])\n",
    "            if a + b == num:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num + 1):\n",
    "            rev, x = 0, i\n",
    "            while x:\n",
    "                rev = rev * 10 + x % 10\n",
    "                x //= 10\n",
    "            if i + rev == num:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        n = len(str(num))\n",
    "        if num==0:\n",
    "            return True\n",
    "        for i in range(int(10**(n-2)), 10**n):\n",
    "            if i+int((str(i)[::-1]))==num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        return any(i + int(str(i)[::-1]) == num for i in range(0, num + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        if not num: return True\n",
    "        N = len(str(num))\n",
    "        for r in [10**(N-1), 10**(N-2)]:\n",
    "            if r < 1: continue\n",
    "            q = deque([[num, 1, r]])\n",
    "            while q:\n",
    "                n, l, r = q.popleft()\n",
    "                divide = l + r\n",
    "                nn, rem = divmod(n, divide)\n",
    "                # print(n, l, r, divide, rem, nn)\n",
    "                if not nn: continue\n",
    "                if l == r and nn > 9 or nn > 19: continue\n",
    "                if not rem: return True\n",
    "                l *= 10\n",
    "                r //= 10\n",
    "                if l > r: continue\n",
    "                if nn <= 18:\n",
    "                    q.append([rem, l, r])\n",
    "                q.append([rem+divide, l , r])\n",
    "        return False \n",
    "                \n",
    "        # 181 - 101 = 80"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        if not num:\n",
    "            return True\n",
    "        for i in range(num,0,-1):\n",
    "            if i+int(str(i)[::-1])==num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        # return any(i+int(str(i)[::-1]) == num for i in range(num+1))\n",
    "\n",
    "        # -----------------------------\n",
    "        for i in range(num + 1):\n",
    "            rev, x = 0, i\n",
    "            while x:\n",
    "                rev = rev * 10 + x % 10\n",
    "                x //= 10\n",
    "            if i + rev == num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 暴力枚举，每次取十进制最低位手动反转\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num + 1):\n",
    "            x, rev = i, 0\n",
    "            while x:\n",
    "                rev = rev * 10 + x % 10\n",
    "                x //= 10\n",
    "            if i + rev == num:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num + 1):\n",
    "            k = i\n",
    "            reverse = 0\n",
    "            while k:\n",
    "                reverse = reverse * 10 + k % 10\n",
    "                k //= 10\n",
    "            if i + reverse == num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num >> 1, num):\n",
    "            if i + int(str(i)[::-1]) == num:\n",
    "                return True\n",
    "        return num == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        def reverse(n):\n",
    "            n_str = str(n)\n",
    "            reverse_n_str = n_str[::-1]\n",
    "            return int(reverse_n_str)\n",
    "        for i in range(num):\n",
    "            if reverse(i) == num-i:\n",
    "                return True\n",
    "        if num == 0:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        map_ = {1 : 1, 2 : 10 }\n",
    "\n",
    "    def parseNum(self, num):\n",
    "        tmp = num\n",
    "        tmpSum, tmpNum = 0, 0\n",
    "        while num:\n",
    "            if tmp == 172:\n",
    "                print(f\":{(tmpSum * 10) + (num % 10)}, ano:{num // 10};\\n\")\n",
    "            tmpSum = (tmpSum * 10) + (num % 10)\n",
    "\n",
    "            num = num // 10\n",
    "        if tmp == 172:\n",
    "            print(f\" num is self.parseNum(i):{tmpSum};\\n\")\n",
    "        return tmpSum\n",
    "\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "\n",
    "        if  num == 0:\n",
    "            return True\n",
    "\n",
    "        for i in range(num):\n",
    "            thisTimeSum = i + self.parseNum(i)\n",
    "            if i == 172:\n",
    "                print(f\" num is self.parseNum(i):{i},{self.parseNum(i)};\\n\")\n",
    "            if thisTimeSum == num:\n",
    "\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num >> 1, num+1):\n",
    "            if i + int(str(i)[::-1]) == num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        # 没啥好的办法 暴力枚举\n",
    "        for i in range(num, -1, -1):\n",
    "            if i + int(str(i)[::-1]) == num:\n",
    "                return True\n",
    "        return False\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(0, num+1):\n",
    "            li = list(str(i))\n",
    "            li.reverse()\n",
    "            if i + int(''.join(li)) == num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num + 1):\n",
    "            if i + int(str(i)[::-1]) == num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        return any(i + int(str(i)[::-1]) == num for i in range(0, num+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(0, num + 1) :\n",
    "            if i + int(str(i)[::-1]) == num :\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        if num == 0:\n",
    "            return True\n",
    "        for i in range(num):\n",
    "            if i + int(str(i)[::-1]) == num:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 暴力枚举，一行代码，使用系统api转字符串后反转数字\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        return any(x + int(str(x)[::-1]) == num for x in range(num + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(0, num + 1):\n",
    "            l = str(i)[::-1]\n",
    "            if i + int(l) == num:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num + 1):\n",
    "            rev, x = 0, i\n",
    "            while x:\n",
    "                rev = rev * 10 + x % 10\n",
    "                x //= 10\n",
    "            if i + rev == num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num, -1, -1):\n",
    "            if i + int(str(i)[::-1]) == num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        \n",
    "        \n",
    "        \n",
    "        for i in range(num+1):\n",
    "            \n",
    "            if i + int(\"\".join(reversed(str(i)))) == num:\n",
    "                \n",
    "                return True\n",
    "            \n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num >> 1, num):\n",
    "            if i + int(str(i)[::-1]) == num:\n",
    "                return True\n",
    "        return num == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        return any(i + int(str(i)[::-1]) == num for i in range(num+1))\n",
    "        # for i in range(num, -1, -1):\n",
    "        #     if i + int(str(i)[::-1]) == num:\n",
    "        #         return True\n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for integer in range(num + 1):\n",
    "            if integer + reverse(integer) == num:\n",
    "                return True \n",
    "        return False \n",
    "\n",
    "def reverse(integer):\n",
    "    reverse_value = 0 \n",
    "    while integer:\n",
    "        reverse_value = reverse_value * 10 + integer % 10\n",
    "        integer //= 10\n",
    "    return reverse_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        return any(i + int(str(i)[::-1]) == num for i in range(num >> 1, num+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        nums = list(map(int, list(str(num))))\n",
    "        def check(i, j, p, b):\n",
    "            while i < j:\n",
    "                head = p*10 + nums[i]\n",
    "                if head <= 18 and (head+b)%10 == nums[j]:\n",
    "                    p, b = 0, (head+b)//10\n",
    "                elif head > int(i==0) and (head-1+b)%10 == nums[j]:\n",
    "                    p, b = 1, (head-1+b)//10\n",
    "                else: return False\n",
    "                i+=1\n",
    "                j-=1\n",
    "            return (nums[i]-b)%2 == 0 if i == j else p == b\n",
    "        return check(0, len(nums)-1, 0, 0) or (nums[0]==1 and check(1, len(nums)-1, 1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num, -1, -1):\n",
    "            if i + int(str(i)[::-1]) == num:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num+1):\n",
    "            rev,x = 0,i\n",
    "            while x:\n",
    "                rev = rev * 10 + x % 10\n",
    "                x //= 10\n",
    "            if i + rev == num:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "        # return any(i + int(str(i)[::-1]) == num for i in range(num+1))\n",
    "\n",
    "\n",
    "        # for i in range(num, -1, -1):\n",
    "        #     if i + int(str(i)[::-1]) == num:\n",
    "        #         return True\n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        return any(i + int(str(i)[::-1]) == num for i in range(num//2, num+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        return any(i + int(str(i)[::-1]) == num for i in range(num//2, num+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num >> 1, num):\n",
    "            if i + int(str(i)[::-1]) == num:\n",
    "                return True\n",
    "        return num == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        if num == 0:\n",
    "            return True\n",
    "        if num % 2 == 0:\n",
    "            left = right = num / 2\n",
    "        else:\n",
    "            left = num // 2\n",
    "            right = left + 1\n",
    "\n",
    "        def reverse(_num: int) -> int:\n",
    "            res = []\n",
    "            while _num != 0:\n",
    "                tmp = _num % 10\n",
    "                _num //= 10\n",
    "                res.append(tmp)\n",
    "            res.reverse()\n",
    "            multiple = 1\n",
    "            _sum = 0\n",
    "            for i in res:\n",
    "                _sum += i * multiple\n",
    "                multiple *= 10\n",
    "            return _sum\n",
    "\n",
    "        while right < num:\n",
    "            if reverse(right) != left:\n",
    "                left -= 1\n",
    "                right += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "\n",
    "        def dwjs(p)->int:\n",
    "            r=0\n",
    "            while p>0:\n",
    "                r=r*10+p%10\n",
    "                p=p//10\n",
    "            return r\n",
    "        for i in range(num+1):\n",
    "            if i +dwjs(i)==num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num + 1):\n",
    "            temp = i + int(str(i)[::-1])\n",
    "            if temp == num:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for x in range(num+1):\n",
    "            if x + int(str(x)[::-1]) == num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num, -1, -1):\n",
    "            j = int(str(i)[::-1])\n",
    "            if i + j == num:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        def rev(num):\n",
    "            revNum = 0\n",
    "            while num > 0:\n",
    "                revNum = revNum * 10 + num % 10\n",
    "                num //= 10\n",
    "            return revNum\n",
    "\n",
    "        for i in range(num + 1):\n",
    "            if i + rev(i) == num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        return any(i+int(str(i)[::-1]) == num for i in range(num+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        # for  i in range(num+1):\n",
    "        #     rev = int(str(i)[::-1])\n",
    "        #     if i + rev ==num:\n",
    "        #         return True \n",
    "        # return False\n",
    "\n",
    "        # return any(i + int(str(i)[::-1]) == num  for i in range(num+1))\n",
    "\n",
    "\n",
    "        for i in range(num+1):\n",
    "            rev = 0 \n",
    "            x = i \n",
    "            while x :\n",
    "                rev = rev * 10 + x  %10\n",
    "                x //=10\n",
    "            if i + rev == num:\n",
    "                return True \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num+1):\n",
    "            res,x=0,i\n",
    "            while x!=0:\n",
    "                res=res*10+x%10\n",
    "                x//=10\n",
    "            if res+i==num:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        # def reverse(n):\n",
    "        #     n_str = str(n)\n",
    "        #     reverse_n_str = n_str[::-1]\n",
    "        #     return int(reverse_n_str)\n",
    "        # for i in range(num):\n",
    "        #     if reverse(i) == num-i:\n",
    "        #         return True\n",
    "        # if num == 0:\n",
    "        #     return True\n",
    "        # return False\n",
    "        return any(i + int(str(i)[::-1]) == num for i in range(0, num + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        # def reverse(n):\n",
    "        #     n_str = str(n)\n",
    "        #     reverse_n_str = n_str[::-1]\n",
    "        #     return int(reverse_n_str)\n",
    "        # for i in range(num):\n",
    "        #     if reverse(i) == num-i:\n",
    "        #         return True\n",
    "        # if num == 0:\n",
    "        #     return True\n",
    "        # return False\n",
    "        # return any(i + int(str(i)[::-1]) == num for i in range(0, num + 1))\n",
    "        for i in range(num + 1):\n",
    "            rev, x = 0, i\n",
    "            while x:\n",
    "                rev = rev * 10 + x % 10\n",
    "                x //= 10\n",
    "            if i + rev == num:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        \n",
    "        nums = list(map(int, list(str(num))))\n",
    "\n",
    "        def check(i, j, p, b):\n",
    "            while i < j:\n",
    "                head = p*10 + nums[i]\n",
    "                if head <= 18 and (head+b)%10 == nums[j]:\n",
    "                    p, b = 0, (head+b)//10\n",
    "                elif head > int(i==0) and (head-1+b)%10 == nums[j]:\n",
    "                    p, b = 1, (head-1+b)//10\n",
    "                else: return False\n",
    "                i+=1\n",
    "                j-=1\n",
    "            return (nums[i]-b)%2 == 0 if i == j else p == b\n",
    "    \n",
    "        return check(0, len(nums)-1, 0, 0) or (nums[0]==1 and check(1, len(nums)-1, 1, 0))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        if num==0:\n",
    "            return True\n",
    "        for i in range(num//2,num):\n",
    "            if i+int(str(i)[::-1])==num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num + 1):\n",
    "            rev, x = 0, i\n",
    "            while x:\n",
    "                rev = rev * 10 + x % 10\n",
    "                x //= 10\n",
    "            if i + rev == num:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\r\n",
    "        return any(num == i + int(str(i)[::-1]) for i in range(num + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        \n",
    "        nums = list(map(int, list(str(num))))\n",
    "\n",
    "        def check(i, j, p, b):\n",
    "            while i < j:\n",
    "                head = p*10 + nums[i]\n",
    "                if head <= 18 and (head+b)%10 == nums[j]:\n",
    "                    p, b = 0, (head+b)//10\n",
    "                elif head > int(i==0) and (head-1+b)%10 == nums[j]:\n",
    "                    p, b = 1, (head-1+b)//10\n",
    "                else: return False\n",
    "                i+=1\n",
    "                j-=1\n",
    "            return (nums[i]-b)%2 == 0 if i == j else p == b\n",
    "    \n",
    "        return check(0, len(nums)-1, 0, 0) or (nums[0]==1 and check(1, len(nums)-1, 1, 0))\n",
    "\n",
    "# 作者：洛必达泉\n",
    "# 链接：https://leetcode.cn/problems/sum-of-number-and-its-reverse/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for  i in range(num+1):\n",
    "            rev = int(str(i)[::-1])\n",
    "            if i + rev ==num:\n",
    "                return True \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        for i in range(num//2, num+1):\n",
    "            reverse = 0\n",
    "            x = i\n",
    "            while x:\n",
    "                reverse *= 10\n",
    "                reverse += x % 10\n",
    "                x = x//10\n",
    "            if reverse+i==num:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "将数字转成字符串N，假设存在一个序列k[i..j]，满足k + rev(k) == N[i..j]，假设i下标相加结果ki+kj的进位为pre，而j下标接收来自j+1位置的进位为suf，i下标接收来自i+1位置的进位为m，则有以下条件成立：\n",
    "1、0 <= sum = ki + kj <= 18，因为位上的最大值为9，相加不会超过18，特别的，如果i==0，由于不存在前导零，要满足sum > 0\n",
    "2、ki + kj + m == 10 * pre + Ni成立，针对i位置（及进位）上的数而言\n",
    "3、(ki + kj + suf) % 10 == Nj成立，针对j位置上的数而言\n",
    "4、如果i、j位置都满足，那么递归检查N[i+1..j-1]是否满足：dfs(i+1, j-1, m, (ki + kj + suf) / 10)。\n",
    "5、递归终止条件：i >= j：如果i == j，由于k序列i位置的和是两个相同数相加的结果，为偶数，ki的取值不影响奇偶性，是否可以跟Ni匹配取决于后进位suf的奇偶性是否跟Ni相同，也即判断suf == Ni & 1即可；如果i > j表示所有数位已匹配，此时后进位suf即为前进位pre，判断pre == suf是否成立。\n",
    "入口函数参数除了dfs(0, len(N)-1, 0, 0)外，如果N0==1，则还可以由len(N)-1位相加并进位为1得到，所以N0==1时还可以调用dfs(1, len(N)-1, 1, 0)参数为入口函数\n",
    "'''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        val = str(num)\n",
    "        n = len(val)\n",
    "\n",
    "        def dfs(i: int, j: int, pre: int, suf: int) -> bool:\n",
    "            if i < j:\n",
    "                m, sum = 0, 10 * pre + ord(val[i])-ord('0') - 0\n",
    "                while m <= 1:\n",
    "                    if (i == 0) <= sum <= 18 and (sum + suf) % 10 == ord(val[j]) - ord('0'):\n",
    "                        return dfs(i + 1, j-1, m, (sum + suf) // 10)\n",
    "                    m += 1\n",
    "                    sum -= 1\n",
    "                return False\n",
    "            return (i == j and suf == (ord(val[i]) - ord('0')) & 1) or (i > j and pre == suf)\n",
    "        return dfs(0,  n-1, 0, 0) or (val[0] == '1' and dfs(1, n-1, 1, 0))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        # return any(i+int(str(i)[::-1]) == num for i in range(num+1))\n",
    "\n",
    "        # -----------------------------\n",
    "        # for i in range(num + 1):\n",
    "        #     rev, x = 0, i\n",
    "        #     while x:\n",
    "        #         rev = rev * 10 + x % 10\n",
    "        #         x //= 10\n",
    "        #     if i + rev == num:\n",
    "        #         return True\n",
    "        # return False\n",
    "\n",
    "        # ---------------------------\n",
    "        nums = list(map(int, list(str(num))))\n",
    "\n",
    "        def dfs(i, j, p, b):\n",
    "            if i == j:\n",
    "                return (nums[i]-b)%2 == 0\n",
    "            if i == j+1:\n",
    "                return p == b\n",
    "            head = p*10 + nums[i]\n",
    "            if head <= 18 and (head+b)%10 == nums[j]:\n",
    "                return dfs(i+1, j-1, 0, (head+b)//10)\n",
    "            elif head > int(i==0) and (head-1+b)%10 == nums[j]:\n",
    "                return dfs(i+1, j-1, 1, (head-1+b)//10)\n",
    "            return False\n",
    "    \n",
    "        return dfs(0, len(nums)-1, 0, 0) or (nums[0]==1 and dfs(1, len(nums)-1, 1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfNumberAndReverse(self, num: int) -> bool:\n",
    "        n = len(str(num))\n",
    "        if num==0:\n",
    "            return True\n",
    "        for i in range(int(10**(n-2)), 10**n//2):\n",
    "            if i+int((str(i)[::-1]))==num:\n",
    "                return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
